// *****************************************************************************
// Filename:    print-two-bst-in-order.cc
// Date:        2012-06-07 23:41
// Author:      Guangda Lai
// Email:       lambda2fei@gmail.com
// Description: TODO(laigd): Put the file description here.
// *****************************************************************************

#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <ctime>
#include <algorithm>

using std::vector;
using std::cout;
using std::endl;

struct Node {
  Node(int x) : data(x) {}
  Node *lson, *rson;
  int data;
  bool operator<(const Node &rhs) const {
    return data < rhs.data;
  }
};

void PrintDfs(const Node *lhs,
              const Node *rhs,
              const bool lhs_lson_printed,
              const bool rhs_lson_printed) {
  if (lhs == NULL) {
    if (rhs == NULL) return;
    if (rhs->lson != NULL) PrintDfs(NULL, rhs->lson);
    cout << rhs->data << ", ";
    if (rhs->rson != NULL) PrintDfs(NULL, rhs->rson);
    return;
  } else if (rhs == NULL) {
    if (lhs->lson != NULL) PrintDfs(lhs->lson, NULL);
    cout << lhs->data << ", ";
    if (lhs->rson != NULL) PrintDfs(lhs->rson, NULL);
    return;
  }
  // Now both lhs and rhs is not NULL.
  if (lhs->data <= rhs->data) {
    if (rhs->lson != NULL) PrintDfs(lhs, rhs->lson
  } else {
  }
}

void PrintRecursively(const Node *lhs, const Node *rhs) {
  PrintDfs(lhs, rhs, false, false);
}

void InitStack(const Node *p, vector<const Node*> *vec) {
  vec->clear();
  if (p == NULL) return;
  vec->push_back(p);
  while (p->lson != NULL) {
    p = p->lson;
    vec->push_back(p);
  }
}

const Node* GetNextNode(vector<const Node*> *vec) {
  if (vec->size() == 0) return NULL;

  const Node *ans = vec->back();
  vec->pop_back();
  if (ans->rson != NULL) {
    const Node *p = ans->rson;
    vec->push_back(p);
    while (p->lson != NULL) {
      p = p->lson;
      vec->push_back(p);
    }
  }
  return ans;
}

void PrintNonRecurisively(const Node *lhs, const Node *rhs) {
  vector<const Node*> lvec, rvec;
  InitStack(lhs, &lvec);
  InitStack(rhs, &rvec);

  const Node *lcur = GetNextNode(&lvec);
  const Node *rcur = GetNextNode(&rvec);

  while (lcur != NULL && rcur != NULL) {
    if (lcur->data <= rcur->data) {
      cout << lcur->data << ", ";
      lcur = GetNextNode(&lvec);
    } else {
      cout << rcur->data << ", ";
      rcur = GetNextNode(&rvec);
    }
  }
  while (lcur != NULL) {
    cout << lcur->data << ", ";
    lcur = GetNextNode(&lvec);
  }
  while (rcur != NULL) {
    cout << rcur->data << ", ";
    rcur = GetNextNode(&rvec);
  }
  cout << endl;
}

Node* InitTestCase(const int l, const int r, vector<Node> *data) {
  if (r <= l) return NULL;
  const int mid = rand() % (r - l) + l;
  Node *p = &(data->at(mid));
  p->lson = InitTestCase(l, mid, data);
  p->rson = InitTestCase(mid + 1, r, data);
  return p;
}

int main() {
  srand(time(0));

  const int kMaxSize = 10;
  vector<Node> ldata, rdata;
  for (int i = 0; i < kMaxSize; ++i) {
    ldata.push_back(Node(rand() % 15));
    rdata.push_back(Node(rand() % 15));
  }
  sort(ldata.begin(), ldata.end());
  sort(rdata.begin(), rdata.end());

  for (int i = 0; i < kMaxSize; ++i) {
    cout << ldata[i].data << ", ";
  }
  cout << endl;

  for (int i = 0; i < kMaxSize; ++i) {
    cout << rdata[i].data << ", ";
  }
  cout << endl;

  const Node *lp = InitTestCase(0, 10, &ldata);
  const Node *rp = InitTestCase(0, 10, &rdata);
  PrintNonRecurisively(lp, rp);
  return 0;
}
